package interview.huawei.tjt.training.dongtaiguihua;

import java.util.Scanner;

/**
 * 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
 *
 * 示例 1:
 *
 * 输入: amount = 5, coins = [1,2,5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
 *
 * 示例 2: 输入: amount = 3, coins = [2] 输出: 0 解释: 只用面额2的硬币不能凑成总金额3。
 *
 * 示例 3: 输入: amount = 10, coins = [10] 输出: 1
 *
 * 注意，你可以假设：
 *
 * 0 <= amount (总金额) <= 5000
 * 1 <= coin (硬币面额) <= 5000
 * 硬币种类不超过 500 种
 * 结果符合 32 位符号整数
 *
 */
public class CoinChangeII {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
            String[] strings = sc.nextLine().split(",");
            int amount = sc.nextInt();
            int[] coins = new int[strings.length];
            for (int i = 0; i < strings.length; i ++) {
                if (!strings[i].equals("")) {
                    coins[i] = Integer.parseInt(strings[i]);
                }
            }
            int[] dp = new int[amount + 1];
            dp[0] = 1;
            // 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
            // 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
            for (int i = 0; i < coins.length; i ++) {
                // 从前往后遍历的话coins里面的元素可以用多次
                for (int j = coins[i]; j <= amount; j ++) {
                    dp[j] += dp[j - coins[i]];
                }
            }
            System.out.println(dp[amount]);
        }

}
